package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;

/**
 * Created with IntelliJ IDEA.
 * 2476. 二叉搜索树最近节点查询
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/22 14:29
 */
public class ClosestNodes {

    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        List<List<Integer>> list = new ArrayList<>();
        TreeSet<Integer> set = new TreeSet<>();
        find(root, set);
        for (Integer query : queries) {
            Integer floor = set.floor(query);
            Integer ceiling = set.ceiling(query);
            int a = floor == null ? -1 : floor;
            int b = ceiling == null ? -1 : ceiling;
            list.add(Arrays.asList(a, b));
        }
        return list;
    }

    private void find(TreeNode node, TreeSet<Integer> set) {
        if (node == null) {
            return;
        }
        set.add(node.val);
        find(node.left, set);
        find(node.right, set);
    }

}
